package xyz.naokeziteng.data_structure.graph_theory;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author hawk
 * @date 2022/10/8
 * @desc 图的深度优先遍历
 **/
public class GraphDFS {

    private Graph G;
    private boolean[] visited;
    private List<Integer> preorder = new ArrayList<>();
    private List<Integer> postorder = new ArrayList<>();


    public GraphDFS(Graph G) {
        this.G = G;
        this.visited = new boolean[G.V()];
        for (int v = 0; v < G.V(); v++) {
            if (!visited[v]) {
                dfs2(v);
            }
        }
    }

    //深度优先遍历
    private void dfs(int v) {
        visited[v] = true;
        preorder.add(v);
        for (int w : G.adj(v)) {
            if (!visited[w]) {
                dfs(w);
            }
        }
        postorder.add(v);
    }

    //深度优先遍历(非递归写法)
    private void dfs2(int s) {
        Stack<Integer> stack = new Stack<>();
        stack.add(s);
        visited[s] = true;
        while (!stack.isEmpty()) {
            int v = stack.pop();
            preorder.add(v);
            for (int w : G.adj(v)) {
                if (!visited[w]) {
                    stack.add(w);
                    visited[v] = true;
                }
            }
        }
    }


    public Iterable<Integer> preorder() {
        return preorder;
    }

    public Iterable<Integer> postorder() {
        return postorder;
    }


    public static void main(String[] args) {
        GraphDFS adjacencyMatrix = new GraphDFS(new Graph("src/main/resources/g.txt"));
        System.out.println(adjacencyMatrix.preorder());
    }
}
